package org.shj.suanfajichu;

// 0/1 背包问题
public class PackageProblem {
	
	private int[] index;
	private int[] w;
	private int[] p;
	private static int count = 0;
	

	public static void main(String[] args){
		PackageProblem pp = new PackageProblem();
		int[] w = {2,3,4, 7,8,5,3};// weight of objects
		int[] p = {1,2,5, 4,3,6,9};//price of objects
		int maxWeight = 30;
		pp.process(w, p, maxWeight);
	}
	
	public void process(int[] w, int[] p, int maxWeight){
		this.w = w;
		this.p = p;
		index = new int[w.length];
		
		int totalP = f(w.length, maxWeight);
		System.out.println(totalP);
		System.out.println(count);
		for(int i = 0 ; i < index.length; i++){
			if(index[i] == 1){
				System.out.println("W" + (i+1) + ",");
			}
		}
	}
	
	/**
	 * 
	 * @param n -- 表示第几个数品， 从 1 开始
	 * @param remainWeight -- 表示背包剩余能容纳的重量
	 * @return
	 */
	public int f(int n, int remainWeight){
		count++;
		if(n == 0){
			return remainWeight < 0 ? Integer.MIN_VALUE : 0;
		}
		if(remainWeight < 0){
			return Integer.MIN_VALUE;
		}else{
			
			int pre = f(n - 1, remainWeight);  //不包括当前物品时，前面所有物品的效益值
			int includeCurrent = f(n-1, remainWeight - w[n - 1]) + p[n - 1]; //包括当前物品时的效益值，注意背包容量应减去当前物品的重量
			if(pre > includeCurrent){
				index[n - 1] = 0;
				return pre;
			}else{
				index[n - 1] = 1;
				return includeCurrent;
			}
		}
	}
}
